// 默认从小到大排序
/**
 * 1. 思路：
 * 从第一个元素开始，重复比较相邻的两项，如果前项大于后项，则交换位置，反之不动
 * 每一轮操作，都会将这一轮最大的元素放置到数组的末尾
 * 如果数组的长度是n，那我们重复完n轮的时候，整个数组就有序了
 *
 * 2. 优化：
 * 通过标志位判断，第一次冒泡的时候就定位到数组是否完全有序，这样最好的时间复杂度优化为On
 *  
 * 3. 复杂度
 * 最好时间复杂度：数组本身有序，只需要比较n-1次，为On
 * 最坏时间复杂度：数组完全逆序，交换次数为n*(n-1)/2,为On^2
 * 平均时间复杂度：On^2
 * 
 */

function betterBubbleSort(arr) {
  const len = arr.length;

  for (let i = 0; i < len; i++) {
    // 区别在这里，我们加了一个标志位
    let flag = false;
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        // 只要发生了一次交换，就修改标志位
        flag = true;
      }
    }

    // 若一次交换也没发生，则说明数组有序，直接放过
    if (flag == false) return arr;
  }
  return arr;
}
